import humanAlgorithm.Cell;
import humanAlgorithm.Grid;
import humanAlgorithm.HiddenSet;
import humanAlgorithm.HiddenSingle;
import humanAlgorithm.Hint;
import humanAlgorithm.HintProducer;
import humanAlgorithm.IndirectHintProducer;
import humanAlgorithm.Locking;
import humanAlgorithm.NakedSet;
import humanAlgorithm.NakedSingle;
import humanAlgorithm.SingleHintAccumulator;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class StrategyBasedSolver implements SudokuAlgorithm {
    private Grid grid;
    private List<HintProducer> directHintProducers;
    private List<IndirectHintProducer> indirectHintProducers;

    @Override
    public List<List<Integer>> solve(List<List<Integer>> puzzle) {
        // make the grid.
        buildGrid(puzzle);
        rebuildPotentialValues();
        buildHintproducers();
        if (solve()) {
            return buildResult();
        } else {
            return puzzle;
        }
    }

    private List<List<Integer>> buildResult() {
        List<List<Integer>> solvedPuzzle = new LinkedList<List<Integer>>();

        for (int i = 0; i < 9; i++) {
            LinkedList<Integer> col = new LinkedList<Integer>();
            solvedPuzzle.add(col);
            for (int j = 0; j < 9; j++) {
                col.add(new Integer(grid.getCellValue(j, i)));
            }
        }
        return solvedPuzzle;

    }

    private void buildGrid(List<List<Integer>> puzzle) {
        grid = new Grid();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                grid.setCellValue(j, i, puzzle.get(i).get(j));
            }
        }
    }

    public void rebuildPotentialValues() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell cell = grid.getCell(x, y);
                if (cell.getValue() == 0) {
                    for (int value = 1; value <= 9; value++)
                        cell.addPotentialValue(value);
                }
            }
        }
        cancelPotentialValues();
    }

    /**
     * Remove all illegal potential values according to the current values of
     * the cells. Can be invoked after a new cell gets a value.
     */
    public void cancelPotentialValues() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                Cell cell = grid.getCell(x, y);
                if (cell.getValue() != 0)
                    cell.clearPotentialValues();
            }
        }
        cancelBy(Grid.Block.class);
        cancelBy(Grid.Row.class);
        cancelBy(Grid.Column.class);
    }

    private void buildHintproducers() {
        directHintProducers = new ArrayList<HintProducer>();

        directHintProducers.add(new HiddenSingle());
        // pointing
        directHintProducers.add(new Locking(true));
        // hidden pair
        directHintProducers.add(new HiddenSet(2, true));
        directHintProducers.add(new NakedSingle());
        // hidden triples
        directHintProducers.add(new HiddenSet(3, true));

        indirectHintProducers = new ArrayList<IndirectHintProducer>();
        // claiming
        indirectHintProducers.add(new Locking(false));
        indirectHintProducers.add(new NakedSet(2));
        indirectHintProducers.add(new HiddenSet(2, false));
        indirectHintProducers.add(new NakedSet(3));
        indirectHintProducers.add(new HiddenSet(3, false));
        indirectHintProducers.add(new NakedSet(4));
        indirectHintProducers.add(new HiddenSet(4, false));

    }

    public boolean solve() {

        while (!isSolved()) {
            SingleHintAccumulator accu = new SingleHintAccumulator();
            try {
                for (HintProducer producer : directHintProducers) {
                    producer.getHints(grid, accu);
                }
                for (IndirectHintProducer producer : indirectHintProducers) {
                    producer.getHints(grid, accu);
                }
            } catch (InterruptedException willHappen) {

            }
            Hint hint = accu.getHint();
            if (hint == null) {
                // no strategy could be applied, = solve failed.
                return false;
            }
            hint.apply();
        }

        return true;
    }

    private boolean isSolved() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                if (grid.getCellValue(x, y) == 0)
                    return false;
            }
        }
        return true;
    }

    /**
     * This is the basic Sudoku rule: If a cell contains a value, that value can
     * be removed from the potential values of all cells in the same block, row
     * or column.
     * 
     * @param partType
     *            the Class of the part to cancel in (block, row or column)
     */
    private <T extends Grid.Region> void cancelBy(Class<T> partType) {
        Grid.Region[] parts = grid.getRegions(partType);
        for (Grid.Region part : parts) {
            for (int i = 0; i < 9; i++) {
                Cell cell = part.getCell(i);
                if (!cell.isEmpty()) {
                    int value = cell.getValue();
                    // Remove the cell value from the potential values of other
                    // cells
                    for (int j = 0; j < 9; j++)
                        part.getCell(j).removePotentialValue(value);
                }
            }
        }
    }
}
